<!DOCTYPE html>
<html lang="zh-cn">
<head>
    <meta charset="utf-8" />
    <title>阶与原根</title>
    <link rel="stylesheet" type="text/css" href="../../css/note.css" />
</head>
<body>

<h2>既约剩余系</h2>

<p class="definition">
  <b>Euler `varphi` 函数 (Euler's totient function)</b>
  设 `n` 为正整数, `1` 到 `n` 中与 `n` 互素的整数个数记为 `varphi(n)`.<br>
  比如, 8 以内与 8 互素的正整数有 1, 3, 5, 7 共 4 个, 于是 `varphi(8)
  = 4`.
</p>

<ol class="proposition">
  [证明参见 <a href="6.html#6-1">Euler 函数</a>]
  <li>对一切正整数 `n gt 1` 有 `varphi(n) lt n`.</li>
  <li>对素数 `p` 有 `varphi(p) = p-1`. `varphi(p^k) = p^k - p^(k-1)`.
    这是因为 `p^k` 以内, `p` 的倍数有 `p^(k-1)` 个.
  </li>
  <li>`varphi` 是积性函数, 即若 `a, b` 互素, 则 `varphi(a b) = varphi(a)
    varphi(b)`.
  </li>
  <li>综上有 `varphi(n) = n prod_(p | n) (1-1/p)`.</li>
</ol>

<table class="col2">
  <tr>
    <td>`n`</td>
    <td>1</td>
    <td>2</td>
    <td>3</td>
    <td>4</td>
    <td>5</td>
    <td>6</td>
    <td>7</td>
    <td>8</td>
    <td>9</td>
    <td>10</td>
    <td>11</td>
    <td>12</td>
  </tr>
  <tr>
    <td>`varphi(n)`</td>
    <td>1</td>
    <td>1</td>
    <td>2</td>
    <td>2</td>
    <td>4</td>
    <td>2</td>
    <td>6</td>
    <td>4</td>
    <td>6</td>
    <td>4</td>
    <td>10</td>
    <td>4</td>
  </tr>
</table>

<div class="playground" value="{ n: 8 }">
<p>求 Euler 函数的值</p>
<script type="text">
module.exports = function (str) {
  let { n } = Playground.parse(str)
  return NT.phi(n)
}
</script>
</div>

<p class="definition">
  <b>既约剩余系</b>
  若 `a -= b (mod n)`, 则由辗转相除法知道 `(a, n) = (b, n)`.
  特别 `(a, n) = 1` 当且仅当 `(b, n) = 1`.  因此可以从模 `n` 的完全剩余系
  `ZZ_n` 中取出一个子集, 称为模 `n` 的既约剩余系:
  <span class="formula">
    `ZZ_n^** = { bar a | (a, n) = 1 } sube ZZ_n`.
  </span>
  显然 `|ZZ_n^**| = varphi(n)`.
</p>

<p class="corollary">
  `ZZ_n^**` 按模 `n` 的乘法构成一个 Abel 群, 单位元是 `bar 1`.
</p>

<ol class="proof">
  乘法交换律与结合律是显然的.
  <li>封闭性. 若 `(a, n) = (b, n) = 1`, 可设
    <span class="formula">
      `x_1 a + y_1 n = 1`, `quad x_2 b + y_2 n = 1`,
    </span>
    相乘得
    <span class="formula">
      `X a b + Y n = 1`,
    </span>
    其中 `X, Y` 为整数. 这说明 `(a b, n) = 1`.
  </li>
  <li>逆元的存在性. 若 `(a, n) = 1`, 可设
    <span class="formula">
      `x a + y n = 1`,
    </span>
    即 `x a -= 1 (mod n)`, `x` 即为 `a` 的逆.
  </li>
</ol>

<p class="proposition">
  若 `G` 为一群, `a in G`, 则左平移变换 `l_a: g mapsto a g` 为双射. 于是
  <span class="formula">
    `a G = {a g | g in G} = G`.
  </span>
  推论: 若 `S = {r_i}_(i=1)^s` 为模 `n` 的完全 (或既约) 剩余系, `a in S`,
  则 `{a r_i}_(i=1)^s` 也是模 `n` 的完全 (或既约) 剩余系.
</p>

<p class="proof">
  由 `a g_1 = a g_2` 两边左乘 `a^-1` 得 `g_1 = g_2`, 故 `l_a` 是单射.
  另一方面, 对任意 `g in G`, 存在 `a^-1 g in G` 被 `l_a` 映到 `g`, 故
  `l_a` 是满射.
</p>

<h2>阶的定义与性质</h2>

<p class="definition">
  设 `a in ZZ_n^**`, 称满足
  <span class="formula">
    `a^d -= 1 (mod n)`
    <span class="label" id="for-index"></span>
  </span>
  的最小正整数 `d` 为 `a` 对模 `n` 的<b>指数</b>或<b>阶</b>,
  记为 `"ord"_n a`. 上下文确定时, 下标 `n` 可以省略.
</p>

<div class="playground" value="{ a: 3, n: 7 }">
<p>求 a 模 n 的阶; 若 a, n 不互素, 返回 NaN.</p>
<script type="text">
module.exports = function (str) {
  const { a, n } = Playground.parse(str)
  return NT.order(a, n)
}
</script>
</div>

<p class="remark">
  对于一般的整数 `a`, 若 `a^d -= 1 (mod n)`, 则 `(a^d, n) = 1`, 也能推出
  `(a, n) = 1`.  下面总假定 `n gt 1` 且 `(a, n) = 1`, 即 `a in
  ZZ_n^**`.
</p>

<p class="proposition">
  <b>阶的唯一性</b>
  若 `a -= b (mod n)`, 则对任意 `k ge 0`, `a^k -= b^k (mod n)`.
  从而 `a, b` 的阶相等.
</p>

<p class="proposition">
  <b>阶的存在性</b>
  满足 <a class="ref" href="#for-index"></a> 的正整数 `d` 是存在的,
  且 `"ord"_n a lt n`.
</p>

<p class="proof">
  设 `n gt 1`, 因为 `(a, n) = 1`, 可设
  <span class="formula">
    `a^i -= r_i (mod n)`,
    `quad 0 lt r_i lt n`,
    `quad i = 0, 1, cdots, n-1`,
  </span>
  `n` 个余数 `r_i` 只能取 `n-1` 个值, 由鸽巢原理, 必有两个余数相等,
  设 `a^i -= a^j (mod n)`, `i gt j`. 同余式两边同乘 `a^-j` 得
  <span class="formula">
      `a^(i-j) -= 1 (mod n)`.
  </span>
  取 `d = i-j` 即得结论.
</p>

<p> 事实上 `"ord " a` 的上界可进一步降低,
    这就是下面的 Euler-Fermat 定理:
</p>

<p class="theorem">
  <b>Euler-Fermat 定理 (Euler's totitent theorem)</b>
  设 `a in ZZ_n^**`, 则
  <span class="formula">
    `a^(varphi(n)) -= 1 (mod n)`.
  </span>
  特别当 `n` 为素数 `p` 时, 上式即 Fermat 小定理 `a^(p-1) -= 1 (mod p)`.
</p>

<p class="proof">
  设 `{r_i}_(i=1)^(varphi(n))` 是模 `n` 的既约剩余系, 乘 `a` 平移,
  `{a r_i}_(i=1)^(varphi(n))` 也是模 `n` 的既约剩余系. 从而
  <span class="formula">
    `prod r_i -= prod (a r_i) -= a^(varphi(n)) prod r_i` `(mod n)`,
  </span>
  两边约去 `prod r_i` 即得结论.
</p>

<p class="definition">
  由 Euler-Fermat 定理, `"ord"_n a le varphi(n)`.
  当等号成立时, 称 `a` 是模 `n` 的<b>原根 (primitive root)</b>.
</p>
<div class="playground" value="{ n: 7 }">
<p>求模 n 的最小原根, 比如 7 的原根是 3 和 5, 我们输出 3. 若不存在原根则输出 NaN.</p>
<script type="text">
module.exports = function (str) {
  const { n } = Playground.parse(str)
  return NT.primitiveRoot(n)
}
</script>
</div>

<p class="remark">
  `"ord"_n a` 就是 `a` 在群 `ZZ_n^**` 中的阶.
  若 `a` 为原根, 则 `a` 的阶等于群的阶 `varphi(n)`,
  此时 `a` 是群的生成元, 既约剩余系具有循环群的简单结构.
</p>

<p class="lemma">
  若 `x^a -= x^b -= 1 (mod n)`, 这推出 `(x, n) = 1`.
  运用辗转相除知 `x^((a,b)) -= 1 (mod n)`.
</p>

<ol class="corollary" id="cor-index">
  设 `a in ZZ_n^**`, `"ord "a = delta`, 则
  <li>整除性质. `a^k -= 1 (mod n) iff delta | k`.
  </li>
  <li>对数性质. 若 `a^i -= a^j (mod n)`, 则 `i -= j (mod delta)`.</li>
</ol>

<ol class="proof">
  <li>只证必要性.
    设 `n = delta q + r` (`0 le r lt delta`),
    若 `a^n -= 1 (mod m)`, 同余式两边同乘 `a^(-delta q)` 得
    `a^r -= 1 (mod m)`, 再由 `delta` 的最小性知 `r = 0`.
  </li>
  <li>不妨取 `0 le j le i lt delta`, 则
    `a^i -= a^j (mod m) iff a^(i-j) -= 1 (mod m)`, 由 `delta`
    的最小性知 `i-j = 0`, 即 `i -= j (mod delta)`.
  </li>
</ol>

<p class="proof">
  1. 的另一证法. 利用引理, 若 `a^k -= a^delta -= 1 (mod n)`, 则 `a^((k,
  delta)) -= 1 (mod n)`. 由 `delta` 的最小性知道 `(k, delta) = delta`,
  即 `delta | k`.
</ol>

<ol class="remark">
  <li>由结论 1 知道, `delta | varphi(m)`, 且 `a^k` (`k = 0, 1, 2, cdots`)
    模 `n` 的余数以 `delta` 为周期重复.</li>
  <li>由结论 2 知道, 在一个周期内, `a^k` (`k = 0, 1, cdots, delta-1`)
    模 `n` 的 `delta` 个余数两两不同.
    特别当 `a` 是原根时, 这 `delta = varphi(n)` 个数构成模 `n`
    的既约剩余系.
  </li>
</ol>

<p class="remark">
  若 `a^x = b (mod n)`, 则 `x` 称为 `b` (关于模 `n`, 以 `a` 为底)
  的<b>离散对数</b>. 由结论 2 知道, 离散对数若存在,
  则它关于模 `delta = "ord "a` 是唯一的.
</p>

<ol class="example">
  讨论模 `m = 2^n` 的指数与原根. 此时有 `varphi(2^n) = 2^(n-1)`.
  <li>模 `m = 2, 4` 时有原根;</li>
  <li>`n ge 3` 时, 模 `m = 2^n` 无原根.  事实上对任意奇数 `a` 有
    <span class="formula">
      `a^(2^(n-2)) -= 1 (mod 2^n)`.
    </span>
    由于 `varphi(2^n) = 2^(n-1) gt 2^(n-2)`, 故此时无原根;
  </li>
  <li>`n ge 3` 时, `"ord"_m 5 = 2^(n-2)`.
    这时数字 5 是原根这一角色的一个 "替代品".
  </li>
</ol>

<ol class="proof">
  <li>`m = 2` 时, `1` 是原根; `m = 4` 时, `"ord"(-1) = 2`, 故 `-1` 是原根.
  </li>
  <li>对 `n` 进行归纳. 设 `a = 2t+1`, 则 `n = 3` 时
    <span class="formula">
      `a^2 = 4t(t+1) + 1 -= 1 (mod 2^3)`,
    </span>
    结论成立. 假设结论对整数 `n ge 3` 成立, 则对 `n+1` 有
    <span class="formula">
      `2^(n+1) | (a^(2^(n-2))-1)(a^(2^(n-2))+1)`
      `= a^(2^(n-1)) - 1`,
    </span>
    结论也成立.
  </li>
  <li>
    2. 中已经证明 `"ord"_m 5 | 2^(n-2)`, 因而只需证 `"ord"_m 5 !|
    2^(n-3)`, 即证
    <span class="formula">
      `5^(2^(n-3)) !-= 1 (mod 2^n)`, `quad n ge 3`.
    </span>
    对 `n` 进行归纳. `n=3` 时结论成立. 假设结论对整数 `n ge 3` 成立,
    则 `n+1` 时, 由于
    <span class="formula">
      `5^(2^(n-3)) -= 1 (mod 2^(n-1))`, `quad n ge 3`.
    </span>
    可设 `5^(2^(n-3)) = 2^(n-1) s + 1`, 于是
    <span class="formula">
      `5^(2^(n-2)) = (2^(n-1) s + 1)^2`
      `= 2^n s(2^(n-2) s + 1) + 1`.
    </span>
    由归纳假设, `2 !| s`, 因此 `5^(2^(n-2)) !-= 1 (mod 2^(n+1))`.
  </li>
</ol>

<ol class="property">
  阶的若干计算性质.
  <li>`n | m rArr` `"ord"_n a | "ord"_m a`;</li>
  <li>若 `(m, n) = 1`, 则 `"ord"_(m n) a = ["ord"_m a, "ord"_n a]`;
  </li>
</ol>

<ol class="proof">
  <li>只需注意 `n | m` 时, `a^delta -= 1 (mod m) rArr
    a^delta -= 1 (mod n)`;
  </li>
  <li>分别记 `"ord"_m a = M`, `"ord"_n a = N`, `"ord"_(m n) a = delta`.
    由 1. 得 `[M, N] | delta`. 另一方面, 有
    <span class="formula">
      `a^([M,N]) -= 1 (mod m)`,
      `quad a^([M,N]) -= 1 (mod n)`,
    </span>
    由 `(m, n) = 1` 得 `a^([M,N]) -= 1 (mod m n)`, 因此 `delta
    | [M,N]`.
  </li>
</ol>

<p class="remark">
  求模 `n` 的阶, 只需作分解 `n = prod n_i = prod p_i^(a_i)`, 就有
  <span class="formula">
    `"ord"_n a = ["ord"_(n_1) a, cdots, "ord"_(n_r) a]`.
  </span>
</p>

<ol class="property enum">
  <b>阶数公式</b> 设 `a, b in ZZ_n^**`:
  <li>逆元的阶. `"ord"(a^-1) = "ord "a`;</li>
  <li>乘积的阶. `"ord"(a b) = "ord "a * "ord "b` 当且仅当
    `("ord "a, "ord "b) = 1`;
  </li>
  <li>幂的阶. `"ord"(a^k) = delta//(k, delta)`, 其中 `delta = "ord "a`.
    特别,
    <ol>
      <li>若 `delta = s t`, 则 `"ord"(a^s) = t`;</li>
      <li>`"ord"(a^k) = "ord "a` 当且仅当 `(k, delta) = 1`.</li>
    </ol>
  </li>
</ol>

<ol class="proof">
  <li>只需注意对任意 `k ge 0`, `a^k -= 1 (mod n)`
    当且仅当 `a^-k -= 1 (mod n)`.
  </li>
  <li>分别记 `a, b, a b` 的指数为 `A, B, delta`. 先证必要性:
    我们有 `(a b)^([A,B]) -= 1 (mod n)`, 故 `A B = delta | [A,B]`.
    这推出 `(A, B) = 1`.<br/>
    再证充分性. 一方面有
    <span class="formula">
      `(a b)^(A B) -= 1 (mod n)`,
    </span>
    故 `delta | A B`; 另一方面
    <span class="formula">
      `a^(delta B) = a^(delta B) b^(delta B) -= (a b)^(delta B) -= 1 (mod n)`,
    </span>
    故 `A | delta B`, 再由 `(A, B) = 1` 得 `A | delta`;
    同理 `B | delta`. 再次由 `(A, B) = 1` 得 `A B | delta`.
  </li>
  <li>
    记 `"ord"(a^k) = l`, `(k, delta) = d`. 一方面,
    <span class="formula">
        `(a^k)^(delta // d) = (a^delta)^(k//d) -= 1 (mod n)`,
    </span>
    故 `l | delta/d`; 另一方面
    <span class="formula">
        `a^(k l) = (a^k)^l -= 1 (mod n)`,
    </span>
    故 `delta | k l`, 即 `delta/d | k/d l`.
    因为 `(delta/d, k/d) = 1`, 所以 `delta/d | l`.
    综上有 `l = delta/d`.
  </li>
</ol>

<p class="corollary">
  <b>原根的数目</b>
  `ZZ_n^**` 中若存在原根, 则原根的数目为 `varphi(varphi(n))`.
</p>

<p class="proof">
  记 `"ord "a = delta`.
  由幂的阶数公式, `ZZ_n^**` 中至少有
  <span class="formula">
    `a^k`, `quad 0 le n lt delta`, `(k, delta) = 1`
  </span>
  这 `varphi(delta)` 个数的阶等于 `delta`.
  特别当 `a` 为原根时即得结论.
</p>

<ol class="theorem">
  <b>给定阶元素的存在性</b>
  <li>若 `(m, n) = 1`, 则对任意 `a, b`, 存在 `c` 使得
    `"ord"_(m n) c = ["ord"_m a, "ord"_n b]`.
  </li>
  <li>对任意 `a, b`, 存在 `c` 使得关于模 `n` 有
    `"ord "c = ["ord "a, "ord "b]`.
  </li>
</ol>

<ol class="proof">
  <li>因为 `(m, n) = 1`, 由孙子定理, 同余方程组
    <span class="formula">
      `x -= a (mod m)`, `quad x -= b (mod n)`
    </span>
    存在唯一解 `x -= c (mod m n)`.
    因为 `c` 和 `a, b` 分别关于模 `m, n` 同余, 所以
    `"ord"_m c = "ord"_m a`, `"ord"_n c = "ord"_n b`.
    再由 `"ord"_(m n) c = ["ord"_m c, "ord"_n c]` 即得结论.
  </li>
  <li>分别记 `A = "ord "a`, `B = "ord "b`, `eta = [A, B]`. 作分解
    <span class="formula">
      `A = a_1 a_2`, `quad B = b_1 b_2`,<br/>
      其中 `(a_2, b_2) = 1`, `quad a_2 b_2 = eta`.
    </span>
    这样的分解是可行的: 设素因子 `p` 在 `eta` 中的次数为 `k`,
    则 `p` 在 `A, B` 中的次数较高的那个也等于 `k`.
    对 `eta` 的每个素因子都如此分类即可得到 `a_2, b_2`.<br/>
    现在由阶数公式,
    <span class="formula">
      `"ord"(a^(a_1)) = a_2`, `quad "ord"(b^(b_1)) = b_2`,
    </span>
    取 `c = a^(a_1) b^(b_1)`, 由乘积的阶数公式,
    <span class="formula">
      `"ord "c = "ord"(a^(a_1) b^(b_1)) = a_2 b_2 = eta`.
    </span>
  </li>
</ol>

<h2>原根存在的充要条件</h2>

<p class="theorem">
  模 `m` 有原根的充要条件是
  <span class="formula">
    `m = 1, 2, 4, p^n, 2p^n`.
  </span>
  其中 `p` 是奇素数, `n ge 1`.
</p>

<p class="proof">
  先证必要性, 充分性将在下文分几个定理完成证明.
  ??
</p>

<ol class="example">
  `p` 为素数, `p !| n`, 则
  <li>同余方程 `x^k -= 1 (mod p)` 共有 `(p-1, k)` 个解;</li>
  <li>同余方程 `x^k -= n (mod p)` 有 `0` 个或 `(p-1, k)` 个解.</li>
</ol>

<ol class="proof">
  <li>设 `g` 是模 `p` 的原根, `x = g^r`, 则
    <span class="formula">
      `g^(r k) -= 1(mod p)`
      `iff p-1 | r k`
      `iff (p-1)/((p-1,k)) | r`.
    </span>
    因此这样的 `r` 共有 `(p-1, k)` 个.
  </li>
  <li>线性叠加原理: 若 `x^k -= n (mod p)` 有解, 设为 `a`,
    我们可以建立"齐次方程" `x^k -= 1 (mod p)` 的解集 `S` 到 "非齐次方程"
    `x^k -= n (mod p)` 的解集 `T` 之间的映射:
    <span class="formula">
      `eta: S to T`,<br>
      `s mapsto a s`
    </span>
    容易验证, 若 `s^k -= 1 (mod p)`, 则 `(a s)^k -= n (mod p)`, 即 `a s in
    T`.
    `eta` 是左平移变换因而是双射, 这说明 `|S| = |T|`.
  </li>
</ol>

<p class="example">
  我们知道, `1//7 = 0. dot 1 4285 dot 7`, 其循环节恰有 `7-1 = 6` 位.
  在 100 以内, 除 2 以外, 满足 `1//n` 的循环节恰有 `n-1`
  位这一性质的正整数 `n` 有:
  <span class="formula">
    7, 17, 19, 23, 29, 47, 59, 61, 97.
  </span>
  它们都是素数以外, 还有什么共同特点?
</p>

<p class="solution">
  共同特点是: 10 是模 `n` 的原根.
  原因是若 `10^d -= 1 (mod n)`, 即 `n | 10^d - 1`, 则分数 `1//n`
  可以化为循环节 `d` 位的循环小数. 如 `10^6 -= 1 (mod 7)`, 则
  <span class="formula">
    `1/7 = 142857/999999 = 0. dot 1 4285 dot 7`.
  </span>
  又如 `10^6 -= 1 (mod 13)`, 则
  <span class="formula">
    `1/13 = 076923/999999 = 0. dot 0 7692 dot 3`.
  </span>
  因此, 当 `(10, n) = 1` 时, 循环节的长度就是 10 模 `n` 的指数.
  要使循环节恰有 `n-1` 位, 就要求 10 模 `n` 的指数等于 `n-1`;
  这当且仅当 `n` 是素数, 且 10 是模 `n` 的原根.
</p>

<p class="example">
  [<a href="https://www.bilibili.com/video/BV1SK4y1974A">manim 短篇 离散猫变换</a>]
  设 `bm A = [2, 1; 1, 1]`, `bm I = [1, 0; 0, 1]`.
  依次取 `m = 11, 59, 2855`,
  求 `"ord"_m bm A`, 即求最小的正整数 `n` 使得
  <span class="formula">
    `bm A^n -= bm I (mod m)`.
  </span>
</p>

<ol class="solution">
  `bm A` 是对称矩阵, 因此可以对角化, 即存在模 `m` 可逆矩阵 `bm P` 使得
  <span class="formula">
    `bm A = bm P^-1 bm D bm P`,
    `quad bm D = [x, ; , y]`.
  </span>
  其中 `x, y` 是 `bm A` 模 `m` 的特征值.
  若 `bm A^n -= bm I (mod m)`, 必有 `bm D^n -= bm I (mod m)`, 即
  <span class="formula">
    `{ x^n -= 1; y^n -= 1 :} (mod m)`.
  </span>
  注意 `|bm A| = 1`, 所以不论 `m`
  取何值, `bm A` 总是非奇异的, 这蕴含 `x^n !-= 0, y^n !-= 0 (mod m)`,
  特别当 `m` 为素数时, 上面的方程组总是有解.
  <li>`m = 11` 时, 由 `x + y -= 3, x y -= 1(mod 11)`, 利用求根公式得
    <span class="formula">
      `x, y -= (3 +- sqrt 5)//2`
      `-= (3 +- 4) * 6`
      `= -2, 5 (mod 11)`
    </span>
    `mod 11` 下 `"ord" (-2) = "ord" 5 = 5`, 取最小公倍数得到
    `"ord"_11 bm A = 5`.
  </li>
  <li>`m = 59` 时特征值为 `(3 +- 8) * 30 -= -24, -32 (mod 59)`.
    从而 `"ord"_59 bm A` `= lcm("ord"(-24), "ord"(-32))`
    `= lcm(29, 29) = 29`.
  </li>
  <li>`m = 2855 = 5 * 571` 时, 模 `5` 的特征值为 `-1 (mod 5)` (2 重根),
    `"ord"_5 (-1) = 2`. 模 `571` 的特征值为 `(3 +- 24) * 286 -= 299, 275
    (mod 571)`, 且 `"ord"_571 299 = "ord"_571 275 = 285`.
    从而 `"ord"_2855 bm A = 2 * 285 = 570`.
  </li>
</ol>

<h2>分圆多项式</h2>

<p class="definition">
  设 `lambda in CC`, 若 `n` 是使得 `lambda^n = 1` 成立的最小正整数,
  则称 `lambda` 的阶为 `n`, 记为 `"ord"lambda = n`.
  <b>分圆多项式 (或割圆多项式)</b>定义为
  <span class="formula">
    `phi_n(x) = prod_("ord"lambda = n) (x - lambda)`.
  </span>
  `phi_n(x)` 的所有根称为 `n` 次<b>本原单位根</b>
  <span class="formula">
    `Theta_n = {zeta_n^k | (k, n) = 1 }`,
    `quad zeta_n = "e"^(2pi"i"//n)`.
  </span>
  因此 `phi_n(x)` 的次数就等于 `|Theta_n| = varphi(n)`.
</p>

<p class="proposition">
  若 `lambda, mu` 是两个 `n` 次本原单位根, 则存在与 `n` 互素的整数 `m`
  使得 `mu = lambda^m`.
</p>

<p class="proof">
  `lambda = zeta_n^j`, `mu = zeta_n^k`,
  `(j, n) = (k, n) = 1`, 只需取 `m` 使得 `j m -= k (mod n)`, 就有
  `lambda^m = zeta_n^(j m) = zeta_n^k = mu`.
</p>

<p class="remark">
  本原单位根与原根的概念不同. 原根 `r` 可以生成整个既约剩余系 `1, r, r^2,
  cdots`, 而本原单位根无此性质.
</p>

<p class="proposition">
  `x^n-1 = prod_(d | n) phi_d(x)`.
</p>

<p class="proof">
  这个等式是对所有 `n` 次单位根按阶分类的结果.
  注意和整数的阶一样, 我们有 `lambda^n = 1 iff "ord"lambda | n`.
</p>

<p>尽管从定义看来不很显然, 但分圆多项式的系数都是整数!</p>

<p class="proposition">
  分圆多项式 `phi_n(x)` 是首 1 的整数系数多项式, 其常数项 `in {1, -1}`.
</p>

<p class="proof">
  首 1 性由定义立即看出. 对 `n` 进行归纳, `n=1` 时 `phi_1(x) = x-1`,
  结论成立. 假设结论对一切 `d lt n` 成立, 考虑 `n` 的情形, 有
  <span class="formula">
    `x^n - 1 = prod_(d | n) phi_d(x) = F(x) phi_n(x)`,
  </span>
  其中
  <span class="formula">
    `F(x) = sum_(j=0)^l a_j x^j`,
    `quad phi_n(x) = sum_(j=0)^(n-l) b_j x^j`,
  </span>
  由归纳假设, `a_0 in {1, -1}`, 比较系数得 `b_0 in {1, -1}`.
  又假定 `b_0, b_1, cdots b_(k-1)` 已被证实为整数, 比较两边 `x^k` 的系数知
  <span class="formula">
    `a_0 b_k + sum_(j=0)^(k-1) a_(k-j) b_j`
  </span>
  为整数, 因此 `a_0 b_k` 为整数, 从而 `b_k` 为整数.
</p>

<table class="col2">
  <tr>
    <th>`n`</th>
    <th>`phi_n(x)`</th>
    <th>`n`</th>
    <th>`phi_n(x)`</th>
  </tr>
  <tr>
    <td>1</td>
    <td>`x-1`</td>
    <td>6</td>
    <td>`x^2-x+1`</td>
  </tr>
  <tr>
    <td>2</td>
    <td>`x+1`</td>
    <td>7</td>
    <td>`x^6+x^5+x^4+x^3+x^2+x+1`</td>
  </tr>
  <tr>
    <td>3</td>
    <td>`x^2+x+1`</td>
    <td>8</td>
    <td>`x^4+1`</td>
  </tr>
  <tr>
    <td>4</td>
    <td>`x^2+1`</td>
    <td>9</td>
    <td>`x^6+x^3+1`</td>
  </tr>
  <tr>
    <td>5</td>
    <td>`x^4+x^3+x^2+x+1`</td>
    <td>10</td>
    <td>`x^4-x^3+x^2-x+1`</td>
  </tr>
</table>

<p>`n = 105` 时, 分圆多项式的系数中首次出现 `{1, -1, 0}` 以外的数:
  <span class="formula">
    `phi_105(x) = x^48+x^47+x^46-x^43-x^42- color(red)2 x^41-x^40-x^39+x^36+x^35+x^34`
    `+x^33+x^32+x^31-x^28-x^26-x^24-x^22-x^20+x^17+x^16+x^15+x^14+x^13`
    `+x^12-x^9-x^8-color(red)2 x^7-x^6-x^5+x^2+x+1`.
  </span>
</p>

<p class="proposition">
  设 `a ge 1`, 当 `n = p^a` (`p` 为素数) 或 `2p^a` (`p` 为奇素数) 时,
  分圆多项式的形式比较简单:
  <span class="formula">
    `phi_(p^a)(x)`
    `= phi_(2p^a)(-x)`
    `= sum_(k=0)^(p-1) x^(k p^(a-1))`
    `= (x^(p^a)-1)/(x^(p^(a-1))-1)`.
  </span>
</p>

<ol class="proof">
  <li>`n = p^a` 次的本原单位根有
    <span class="formula">
      `Theta_n = {zeta_n^k | (k, n) = 1}` `= {zeta_n^k | p !| k}`,
    </span>
    所以 `phi_n(x)` 就等于从 `x^n-1` 中排除掉以下因子:
    <span class="formula">
      `prod_(k=1)^(p^(a-1)) (x-zeta_n^(p k))`
      `= prod_(k=1)^(p^(a-1)) (x-zeta_(p^(a-1))^k)`
      `= x^(p^(a-1)) - 1`.
    </span>
  </li>
  <li>设 `p` 为奇素数. 下证 `lambda` 的阶为 `p^a` 当且仅当 `-lambda` 的阶为
    `2p^a`.<br>
    若 `"ord"lambda = p^a`, 容易验证 `(-lambda)^(2p^a) = 1`;
    又对任意 `d | 2p^a`, 若 `(-lambda)^d = 1`, 则 `d` 必为偶数,
    有 `lambda^d = 1`; 因而 `2 b` 必为 `p^a` 的倍数, 只能 `d = 2 p^a`.
    这指出 `-lambda` 的阶是 `2p^a`.<br>
    反之若 `-lambda` 的阶为 `2p^a`, 则 `(-lambda)^(p^a)` 只能是 `-1`.
    两边约去 `(-1)^(p^a)` 得 `lambda^(p^a) = 1`.
    又对任意 `d | p^a`, 若 `lambda^d = 1`, 则 `(-lambda)^(2d) = 1`,
    迫使 `d = p^a`, 即 `lambda` 的阶为 `p^a`.
    <br>
    另一方面, `varphi(p^a) = varphi(2p^a) = p^a-p^(a-1)`,
    这指出 `p^a` 次本原单位根和 `2p^a` 次本原单位根一样多.
    因此, 只要将 `phi_(p^a)(x)` 中的 `x` 换成 `-x`,
    就得到 `phi_(2p^a)(x)`.
  </li>
</ol>

<p class="example">
  `f(x) = phi_(p^a)(x)` 在 `QQ` 上不可约.
</p>

<p class="proof">
  令
  <span class="formula">
    `g(x) = f(x+1)`
    `= ((x+1)^(p^a)-1)/((x+1)^(p^(a-1))-1)`
    `-= (x^(p^a)+1-1)/(x^(p^(a-1))+1-1)`
    `-= x^(p^a - p^(a-1)) (mod p)`.
  </span>
  这表明 `g(x)` 除最高项系数为 1 之外, 其余系数均为 `p` 的倍数.
  另一方面 `g(x)` 的常数项为 `g(0) = f(1) = p`; 由 Eisenstein 判别法知
  `g` 不可约, 因此 `f` 也不可约.
</p>

<p class="proposition">
  任意分圆多项式在 `ZZ` 上不可约, 从而由 Gauss 引理, 在 `QQ` 上也不可约.
</p>

<ol class="proof">
  <li>反设 `phi_n(x) = g(x) h(x)`, 其中 `g, h` 是首 1 的, 次数 `ge 1`
    的整系数多项式, 且 `g` 不可约. 任取 `g` 的一根 `lambda` 和素数 `p !|
    n`, 下证 `lambda^p` 也是 `g` 的根.
  </li>
  <li>由分圆多项式定义, `lambda^p` 是 `phi_n(x)` 的根; 若它不是 `g` 的根,
    则它是 `h` 的根, 因此 `lambda` 是 `g(x)` 和 `h(x^p)` 的公共根.
    现在对 `p` 取模, 由 Fermat 小定理,
    <span class="formula">
      `h(x^p) -= h(x) (mod p)`,
    </span>
    即 `g` 和 `h` 在模 `p` 意义下有公共根.
    下证 `phi_n(x) = g(x) h(x)` 在模 `p` 意义下无重根, 从而引出矛盾.
  </li>
  <li>`phi_n(x)` 是 `x^n-1` 的因子, 故只需证 `f(x) = x^n-1` 模 `p`
    意义下无重根.  事实上, `(f(x), f'(x)) = (x^n-1, n x^(n-1)) = 1`,
    因此它无重根.
  </li>
  <li>综上有 `lambda^p` 是 `g` 的根.
    任取 `n` 次本原单位根 `lambda^m`, `(m, n) = 1`,
    作素因子分解 `m = prod p_i`, 则
    <span class="formula">
      `lambda^m = ((lambda^(p_1))^(p_2))^cdots`
    </span>
    也是 `g` 的根. 这就是说 `phi_n(x)` 的所有根都是 `g` 的根,
    从而 `phi_n(x) = g(x)` 是不可约多项式.
  </li>
</ol>

<p class="definition">
  <b>分圆域</b> 是多项式 `x^n - 1 in QQ[x]` 的分裂域.
  将任一本原单位根 `zeta_n` 加到 `QQ` 中都得到同一个分圆域 `QQ(zeta_n)`,
  且 `phi_n(x)` 是 `zeta_n` 在 `QQ` 上的最小多项式.
  `QQ(zeta_n) // QQ` 是 Galois 扩张, 扩张次数为 Euler 函数 `varphi(n)`.
  其 Galois 群 `Gal(QQ(zeta_n)//QQ)` 同构于 `ZZ_n^**`.
</p>

<script src="../../js/note.js?type=math"></script>
<script src="../../js/playground.js"></script>
<script src="../../code/nt.js"></script>
</body>
</html>
